package com.zp.self.module.level_4_算法练习.算法.广度优先搜索;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author By ZengPeng
 */
public class 力扣_1091_二进制矩阵中的最短路径 {
    //测试
    public static void main(String[] args) {
        System.out.println(new 力扣_1091_二进制矩阵中的最短路径().shortestPathBinaryMatrix(new int[][]{{0,0,0},{1,1,0},{1,1,0}}));
        System.out.println(new 力扣_1091_二进制矩阵中的最短路径().shortestPathBinaryMatrix(new int[][]{{0}}));
        System.out.println(new 力扣_1091_二进制矩阵中的最短路径().shortestPathBinaryMatrix(new int[][] {{0,1,1,0,0,0},{0,1,0,1,1,0},{0,1,1,0,1,0},{0,0,0,1,1,0},{1,1,1,1,1,0},{1,1,1,1,1,0}}));
    }

    /**
    题目：给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
     二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
     路径途经的所有单元格都的值都是 0 。
     路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
     畅通路径的长度 是该路径途经的单元格总数。

     示例 1：
     输入：grid = [[0,1],[1,0]]
     输出：2

     示例 2：
     输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
     输出：4

     示例 3：
     输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
     输出：-1

     分析：【PR 💞💞💞💘💘💘】
         1.动态规划+递归+位图记录：每个节点有8个移动方向：
         记录每个节点到达[n-1,n-1]的最小路径，不能抵达则改为-1
                --完了，方向错了，浪费一卡车时间
         2.动态规划+递归+位图记录: 记录到达 每个为0 的点的最小步骤  --- 深度优先遍历阿  --还会超时
         3.广度优先遍历BFS:
                           (0，0)开始找到距离+1的点，再找到这些点的所有距离+1点，直到找到grid[n-1][n-1],队列两个队列循环切换，先找到当前节点的所有8边节点
                               --执行用时：15 ms, 在所有 Java 提交中击败了46.20%的用户
                  大佬优化：直接在grid数组上操作加法
                               --执行用时：10 ms, 在所有 Java 提交中击败了97.98%的用户
    边界值 & 注意点：
         1.起点 不为0 ，返回-1   [[1]]
         2.只有一个值  [[0]]
         3.卧槽 神龙摆尾  [[0,1,1,0,0,0],[0,1,0,1,1,0],[0,1,1,0,1,0],[0,0,0,1,1,0],[1,1,1,1,1,0],[1,1,1,1,1,0]]
         4.回手掏，把自己给堵死了  [[0,1,0,0,0,0],[0,1,1,1,1,1],[0,0,0,0,1,1],[0,1,0,0,0,1],[1,0,0,1,0,1],[0,0,1,0,1,0]]
     **/
    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0]==1 || grid[grid.length-1][grid.length-1]==1 )
            return -1;
        int[][] point = new int[][]{{-1,-1},{-1,0},{-1,1}   ,{0,-1},{0,1}  ,{1,-1},{1,0},{1,1}};  //八个方向的横纵坐标点变化
        Deque<int[]> deque = new ArrayDeque<>();//记录同距离的节点
        grid[0][0]=1;
        deque.add(new int[]{0,0});
        while (!deque.isEmpty()){
            int[] current = deque.poll();
            for (int i = 0; i < point.length; i++) {
                int x = current[0]+point[i][0];
                int y = current[1]+point[i][1];
                if(x>=0 && x<grid.length && y>=0 && y<grid.length && grid[x][y]==0){
                    deque.add(new int[]{x,y});
                    grid[x][y]=grid[current[0]][current[1]]+1;
                }
            }
        }
        return grid[grid.length-1][grid.length-1]==0?-1:grid[grid.length-1][grid.length-1];

        //3.1 队列两个队列循环切换，先找到当前节点的所有8边节点
/*        if(grid[0][0]==1 || grid[grid.length-1][grid.length-1]==1 )
            return -1;
        Deque<int[]> deque = new ArrayDeque<>();
        Deque<int[]> dequeAround = new ArrayDeque<>();
        boolean[][] see = new boolean[grid.length][grid.length];
        //八个方向的横纵坐标点变化
        int[][] point = new int[][]{{-1,-1},{-1,0},{-1,1}   ,{0,-1},{0,1}  ,{1,-1},{1,0},{1,1}};
        deque.add(new int[]{0,0});
        see[0][0] =true;
        int path =1;
        while (!deque.isEmpty()){
            while (!deque.isEmpty()){
                int[] current = deque.poll();
                if(current[0]==grid.length-1 && current[1]==grid.length-1) return  path;
                for (int i = 0; i < point.length; i++) {
                    int x = current[0]+point[i][0];
                    int y = current[1]+point[i][1];
                    if(x>=0 && x<grid.length && y>=0 && y<grid.length && grid[x][y]==0 && !see[x][y]){
                        see[x][y] =true;
                        dequeAround.add(new int[]{x,y});
                    }
                }
            }
            path++;
            deque = dequeAround;
            dequeAround=new  ArrayDeque<>();
        }
        return -1;*/
    }

    // fail --   2.动态规划+递归+位图记录: 记录到达 每个为0 的点的最小步骤  --- 深度优先遍历阿  --还会超时
    private int bfs(int[][] grid, int x, int y, int numb) {
        if(x<0 || x==grid.length ||y<0 || y==grid[0].length ||grid[x][y]==1)
            return -1;
        if(grid[x][y]==0){//需要找3个方向的最小值
            int min=Integer.MAX_VALUE;
            int bfs = bfs(grid, x + 1, y + 1, numb + 1);
            if(bfs!=-1 ) min = bfs;

            bfs =bfs(grid,x+1,y,numb+1);
            if(bfs!=-1 ) min = Math.min(min,bfs);

            bfs =bfs(grid,x,y+1,numb+1);
            if(bfs!=-1) min = Math.min(min,bfs);

            grid[x][y]=min==Integer.MAX_VALUE?-1:min+1;
        }
        return grid[x][y];
    }
}
